| 翻訳と辞書 |
| partition problem ： ウィキペディア英語版 |
partition problem
In computer science, the partition problem (or number partitioning) is the task of deciding whether a given multiset ''S'' of positive integers can be partitioned into two subsets ''S''1 and ''S''2 such that the sum of the numbers in ''S''1 equals the sum of the numbers in ''S''2. Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem".
There is an optimization version of the partition problem, which is to partition the multiset ''S'' into two subsets ''S''1, ''S''2 such that the difference between the sum of elements in ''S''1 and the sum of elements in ''S''2 is minimized. The optimization version is NP-hard, but can be solved efficiently in practice.
==Examples==
Given ''S'' = , a valid solution to the partition problem is the two sets ''S''1 = and ''S''2 = . Both sets sum to 5, and they partition ''S''. Note that this solution is not unique. ''S''1 = and ''S''2 = is another solution.
Not every multiset of positive integers has a partition into two halves with equal sum. An example of such a set is ''S'' = .
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「partition problem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|